import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName:
 * @author:
 * @Description:
 * @Date
 **/
//二分查找树
public class BinaryTree2<E extends Comparable<E>> {
    private class Node {
        E e;
        Node left;
        Node right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BinaryTree2() {
        root = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    //添加元素非递归实现
    public void add(E e) {
        if (root == null) {
            root = new Node(e);
            size++;
            return;
        }
        //表示父亲节点
        Node p = root;
        while (p != null) {
            if (e.compareTo(p.e) < 0) {
                // 如果 p 的左子树为空，则在 p.left 上放入新的节点
                if (p.left == null) {
                    p.left = new Node(e);
                    size++;
                    return;
                }
                //放入新节点后p.left成为下一个子树的父亲节点
                p = p.left;
            } else if (e.compareTo(p.e) > 0) {
                //如果p的右子树为空，则在p.right上放入新节点
                if (p.right == null) {
                    p.right = new Node(e);
                    size++;
                    return;
                }
                p.right = p;
            } else
                return;
        }
    }

    public void preOrder() {
        preOrder(root);
    }

    //前序遍历的非递归实现，利用系统栈的后进先出原理
    private void preOrder(Node node) {
        Stack<Node> stack = new Stack<>();
        //根节点压入栈
        stack.push(node);
        //只要栈还不为空
        while (!stack.isEmpty()) {
            //出栈
            Node curr = stack.pop();
            System.out.println(curr.e);
            //先压入右孩子，再压入左孩子，这样出栈是就是先左孩子出栈，再右孩子出栈
            if (curr.right != null) {
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }
        }
    }

    //二分查找树层序遍历的实现，利用队列的先进先出的原理
    public void levelOrder() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //先进的先访问，第一次先访问根元素
            Node curr = queue.remove();
            System.out.println(curr.e);
            if (curr.left != null) {
                //如果左子树不为空，进左孩子
                queue.add(curr.left);
            }
            if (curr.right != null) {
                //如果右子树不为空，进右孩子
                queue.add(curr.right);
            }
        }
    }


}
